package com.cat.graphTheory;

import java.util.ArrayList;
import java.util.List;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/number-of-operations-to-make-network-connected/description/https://leetcode.cn/problems/number-of-operations-to-make-network-connected/description/
 * @create 2025/9/18 21:06
 * @since JDK17
 */

public class Solution05 {
    List<List<Integer>> g = new ArrayList<>();
    boolean[] vis;
    int n;

    void dfs(int cur) {
        vis[cur] = true;
        for (int x : g.get(cur)) {
            if (!vis[x]) {
                dfs(x);
            }
        }
    }

    public int makeConnected(int n, int[][] connections) {
        if (connections.length < n - 1) {
            return -1;
        }
        this.n = n;
        vis = new boolean[n];
        int ans = 0, m = connections.length;
        for (int i = 0; i < n; i++) {
            g.add(new ArrayList<>());
        }
        for (int i = 0; i < m; i++) { // 建图
            int from = connections[i][0], to = connections[i][1];
            g.get(from).add(to);
            g.get(to).add(from);
        }

        for (int i = 0; i < n; i++) {
            if (!vis[i]) {
                dfs(i);
                ans++;
            }
        }

        return ans - 1;
    }
}
